package com.peng.leetcode.list;

/**
 * IsPalindrome
 * 234. 回文链表
 * https://leetcode.cn/problems/palindrome-linked-list/
 * 寻找中心节点，反转后半部分链表
 * 从head 和 反转之后的l1 head 循环判断
 *
 * @author: lupeng6
 * @create: 2020/12/21 20:59
 */
public class IsPalindrome1 {

    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    ", next=" + next +
                    '}';
        }
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(2, new ListNode(1, null))));
        System.out.println(new IsPalindrome1().isPalindrome(head));
    }

    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode middle = findMiddle(head);
        ListNode l1 = middle.next;
        middle.next = null;
        l1 = reverse(l1);
        while (l1 != null && head != null) {
            if (l1.val != head.val) {
                return false;
            }
            l1 = l1.next;
            head = head.next;
        }
        return head == null || head.next == null;
    }

    private ListNode reverse(ListNode head) {
        ListNode sentry = new ListNode();
        sentry.next = head;
        while (head.next != null) {
            ListNode del = head.next;
            head.next = head.next.next;

            ListNode n = sentry.next;
            sentry.next = del;
            del.next = n;
        }
        return sentry.next;
    }

    private static ListNode findMiddle(ListNode head) {
        ListNode low = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            low = low.next;
            fast = fast.next.next;
        }
        return low;
    }


}
